package LK_DP;

class DP_Day_1 {
    /*斐波那契数
    * 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。
    * 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：*/
    public int fib(int n) {
        int f0=0;
        int f1=1;
        if (n == 0){
            return f0;
        }
        if (n == 1){
            return f1;
        }
        int fn=0;
        while (n >= 2){
            fn=f0+f1;
            f0=f1;
            f1=fn;
            n--;
        }
        return fn;
    }
    /* 第 N 个泰波那契数
    * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2*/
    public int tribonacci(int n) {
        int t0=0;
        int t1=1;
        int t2=1;
        if (n == 0){
            return t0;
        }
        if (n == 1){
            return t1;
        }
        if (n == 2){
            return t2;
        }
        int sum=0;
        while (n >= 3){
            sum=t0+t1+t2;
            t0=t1;
            t1=t2;
            t2=sum;
            n--;
        }
        return sum;
    }

    public static void main(String[] args) {
        DP_Day_1 test=new DP_Day_1();
        test.fib(4);
    }
}